#include "linked_list.h"


int size(Node* head) {
    if (!head) return 0;
    return 1 + size(head->next);
}


void print(Node* head) {
    std::cout << "[";
    for (Node* curr = head; curr != nullptr; curr = curr->next) {
        std::cout << curr->key;
        if (curr->next != nullptr) std::cout << ", ";
    }
    std::cout << "]" << std::endl;
}


void print(std::vector<int> vec) {
    std::cout << "[";
    for (auto it=std::begin(vec); it != std::end(vec); it++) {
        std::cout << *it;
        if ((it+1) != std::end(vec)) std::cout << ", ";
    }
    std::cout << "]" << std::endl;
}


Node* create_list(std::vector<int> nums) {
    Node* next = nullptr;
    for (auto it = std::rbegin(nums); it != std::rend(nums); it++) {
        Node* curr = new Node(*it, next);
        next = curr;
    }
    return next;
}


/**
 * @brief Insert an element at the head of the linked list.
 * 
 * @param head A reference so that we change it directly
 * @param new_key new data to be added into the current node
 */
void insert(Node*& head, int new_key) {
    Node* curr = new Node(new_key, head);
    head = curr;  // need to be a reference
}


/**
 * @brief Remove the first existing node with key == old_key
 */
void remove(Node*& head, int old_key) {
    if (!head) return;
    if (head->key == old_key) {
        Node* temp = head;
        head = head->next;  // need to be a reference
        delete temp;
    } else {
        remove(head->next, old_key);
    }
}


void insert_after(Node* head, int old_key, int new_key) {
    if (!head) return;
    if (head->key == old_key) {
        Node* curr = new Node(new_key, head->next);
        head->next = curr;
    } else {
        insert_after(head->next, old_key, new_key);
    }
}


void delete_first_element(Node*& head) {
    if (!head) return;
    Node* temp = head;
    head = head->next;
    delete temp;
}


void delete_last_element(Node*& head) {
    if (!head) return;
    if (!head->next) {
        delete head;
        head = nullptr;  // need to be a reference
    } else {
        Node* curr = head;
        while (curr->next && curr->next->next) {
            curr = curr->next;
        }
        delete curr->next;
        curr->next = nullptr;  // make sure the last "next pointer" is null
    }
}


void delete_list(Node*& head) {
    if (!head) return;
    delete_list(head->next);
    delete head;
    head = nullptr;
}


Node* interleave(Node* list1, Node* list2) {
    if (!list1 && !list2) return nullptr;
    if (!list1) return new Node(list2->key, interleave(list1, list2->next));
    if (!list2) return new Node(list1->key, interleave(list1->next, list2));

    Node* n1 = new Node(list1->key);
    Node* n2 = new Node(list2->key);
    n1->next = n2;
    n2->next = interleave(list1->next, list2->next);

    return n1;
}


std::vector<int> to_vector(Node* head) {
    int n = size(head);
    std::vector<int> vec(n);

    int i=0;
    for (Node* curr = head; curr; curr=curr->next) {
        vec[i++] = curr->key;
    }

    return vec;
}
